Recursion and Windows
Volume Number: 1
Issue Number: 11
Column Tag: Lisp Listener
By Andy Cohen, Human Factors Engineer, MacTutor Contributing Editor
MacScheme offers an Alternative
This month I am happy to announce that there is now a third Lisp environment
available for the Mac. The first was XLisp (which is now in version 5, which included
some quickdraw routines), the second was ExperLisp (see below for the current
version number) and the third is called MacScheme from Semantic Micro Systems in
Beaverton, Oregon. MacScheme is an implementation of Scheme, which is actually an
idealized version of Common Lisp which was proposed by Guy Steele. MacScheme is
implemented on the Macintosh in a different way then ExperLisp or XLisp. I will give
the details of how it was developed in a more detailed review in the near future. For
now though I can say that it will have the capability to manipulate over 20,000 cons
cells with just a 512K Mac. I'm also told that a Levco MonsterMac (2 mbyte) using
Macscheme can have approximately 120,000 cons cells. In contrast, ExperLisp can
only create 5,912 cons cells in a 512K Mac and 30,480 in a MonsterMac. Macscheme
however, will not have the bells and whistles that ExperLisp has. There is currently
no way in Macscheme to access the Mac's rom toolbox. John Ulrich, one of the
developers of Macscheme tells me that in time they eventually will be able to access
the toolbox. Macscheme does use the standard Macintosh user-interface. It uses the
menu bar and can produce up to four windows. These windows contain things like a
compiler, an editor, a debugger (!) and a Listener window. It is supposedly as
interactive as ExperLisp. One can compile and evaluate a single line from the Listener
window or compile an entire file. There are two more aspects to Macscheme which I
feel are almost as significant as it's capacity; cost and copy protection. The cost is
extremely low, $125.00 and it is not copy protected. It can easily be put onto a hard
disk or a RAM disk for more speed during startup. As soon as I get Macscheme I will
give a more detailed review. I hope to include some benchmarks and a better
comparison to ExperLisp.
SIMPLE RECURSION
Recursion is one of the most basic control structures in Lisp. To recur is to occur
again. A recursive structure or function is one which is essentially iterative in that
it is repetitive. Recursive structures or functions are different from iterative
procedures in that they call themselves repeatedly in a circular fashion in order to
solve a problem. The recursion ends when the solution is computed. For example,
suppose one needed to know how fast a printer can print a certain number of pages. Let
us assume that we already know it takes .763 minutes per page. We have also just
learned that a certain Masters thesis is 72 pages long. Well, we could just simply
multiply .763 by 72, however that would not be an example of recursion.
Multiplication would be the easy way. Let's try the hard way. What the following will
do is add the time per page (.763) to a variable, which I have called timecount, once
for each page.
(setq timecount 0)
(defun Printtime (pagenum)
(setq timecount (+ timecount .763))
(cond ((= 1 pagenum) timecount)
(t (Printtime (sub1 pagenum)))))
(Printtime 72)
;54.936
When the above is compiled, "timecount" is assigned the value zero. When
"Printtime" is called the value sent with the call is the number of pages (pagenum).
The second line of Printtime reassigns to "timecount" the value of the sum of the
previous value of timecount and the number .763. The next line is a conditional which
tests the value of pagenum. If pagenum is one, the "=" predicate returns "t", the value
of timecount is displayed and the procedure is terminated. If pagenum is not equal to
the number one then the equal predicate returns "nil" and the next line is evaluated.
The third line forces it's evaluation by virtue of the "t" at the beginning of the list.
This list then calls the very same defined function, however the parameter ,"pagenum
is decremented by one. This continues until pagenum equals zero. The time it took the
printer to print the given number of pages is then displayed. In the case of 72 pages it
took 54.936 minutes (it was probably high quality!).
Sometimes it requires more than one function to solve a problem. Two-part
recursion is when one function calls a second and the second function does all the work.
Since we actually need to have the variable "timecount" set to zero every time we use
the function it can be more efficiently implemented in terms of our Lisp environment
as a two-part recursive function.
(defun setup (n)
(setq timecount 0)
(Printtime n))
(defun Printtime (pagenum)
(setq timecount (+ timecount .763))
(cond ((zerop pagenum) timecount)
(t (Printtime (sub1 pagenum)))))
(setup 72)
; 54.936
(setup 90)
;68.67
(setup 12)
;9.156
(setup 32)
;24.416
Given the above, one can now solve the problem without having to compile the
entire source listing everytime. Using "setup" which calls "Printtime" the variable
timecount is initiated without recompiling. Note that the value represented by
variable "n" is passed to Printtime which then assigns it to "pagenum". If one was to
call Printtime after compiling and running the above, the last number assigned to
timecount will still be assigned. Therefore, the number returned is the total of the last
total time plus the number of pages given when Printtime was called by itself.
Recursion is an important feature of Lisp. The above was a very simple example. In
next month's column I'll discuss more complicated recursive functions.
Windows!
Yes, ExperLisp does do windows. After months of saying that I'll show how, I've
finally got around to doing it. As you might already know from previous months, one
may generate a window by simply accessing either the Bunny or Quickdraw graphics
routines available in ExperLisp. In this case the window is the standard graphics
window or "Std_graf" to ExperLisp. "Std_graf" is the term used by ExperLisp in
referring to a window. One may associate a "Std_graf" with their own window by
assigning the special term "newgraph window" and a list containing a set of coordinates
(which correspond to the top left and bottom right corners of the window) to the
chosen term which identifies the window. For my example the term I have chosen is
"Win1". After this assignment is made one must then assign the name "Win1" to the
special term "Std_graf". To assign a title to the window which will be displayed on top
of the window the special term "setwtitle" is used. My sample follows:
(setq Win1 (newgrafwindow '(90 115 290 335))
std_graf Win1))
(Win1 'setwtitle "My First Window")
The above will generate a window which does not contain scroll bars or an expand
corner. Expanding the window or shrinking it however, is possible by placing the
mouse on the lower right corner and dragging it to the desired size. One might note that
after running the above, the window is covered up by the Listener Window. It has to be
selected before it can be changed or moved. This is because when there is no other
functions operating the Listener Window becomes the active window. In order to keep
the programmed window active one must be within a procedure which selected it or a
procedure which is called by a previous procedure which selected the window. Figure 1
is a screen dump of what the window looks like on the ExperLisp desktop. The screen
dump also contains the output generated within the Listener window as a result of the
window creation. Windows can also be selected via quickdraw routines. For example:
(FILLOVAL '(34 67 89 90) dkgrey Win1)
The window is selected by including the window title at the end of the quickdraw
routine. The window can be deleted by using the following:
(CLOSEWINDOW)
One can size a window using the following:
(SIZEWINDOW width height)
One can also HIDEWINDOW, SHOWWINDOW, MOVEWINDOW x y, or SENDBEHIND
window. All of the window primitives are as easy to use as those sampled above.
Putting It All Together
Now lets' put all that has been discussed over the last couple of months together
into a simple bunch of procedures which will allow the user to draw a black rectangle
with the mouse into the window generated by the code described above.
(defun Watch ()
(Win1 'select window)
(prog ()
look
(if ( button) (Mousey (REVERSE (getmouse))))
(go look)))
(defun Mousey (x)
(prog ()
try
(setq inputs (append x (REVERSE(getmouse))))
(framerect inputs)
(eraserect inputs)
(if (not( button)) (halt x) (go try))))
(defun halt (x)
(paintrect (append x (REVERSE (getmouse)))))
(Watch)
The overall structure of the above is the same as that used with the procedures
presented last month which printed the mouse location. When "Watch" is called, the
window "Win1" is selected and brought to the front. The procedure "Watch" also scans
the mouse awaiting a button press. When the button on the mouse is pressed the
X-Yvalues of the mouse position are reversed (to correspond to the top-left of the
quickdraw syntax) and sent in a list as a parameter to the procedure "Mousey". Mousey
appends together a list made up of the passed parameter "x" and a second (REVERSE
(GETMOUSE)). This list is assigned to the symbol "inputs", which is then used in the
FRAMERECT. The FRAMERECT is immediately erased using ERASERECT to give the
outline effect prior to releasing the button and selecting the rectangle size. When the
button is released the procedure "Halt" is called with the exact same value passed to it
as the value passed to "Mousey". It is still the top, left hand corner of our rectangle. In
"Halt" the rectangle is finally drawn using the latest mouse position for the bottom,
right hand corner.
When compiling these routines one should see each function name printed in the
Listener Window as the function is compiled. If the name does not appear and the "I
beam cursor reappears, there is a typo. Chances are it is a problem with the
parentheses. If the names show up but the functions are not initiated, chances are a
parenthesis was left out somewhere. The above should work fine. One of the biggest
disadvantages in using ExperLisp at this time is the poor error messages given when
the programmer has done something wrong. I find that most of my errors are in
leaving out a parenthesis or putting too many in. Parentheses matching is a capability
inherent in an editor which gives some indication to the programmer as to which
parenthesis goes with another. Some Lisp machines actually put the parenthesis in for
the programmer automatically. In version 1.04 of ExperLisp we will be given the
luxury of parenthesis matching. Version 1.04 should be released by the time this
column is in print. This new version of ExperLisp will handle parenthesis matching by
highlighting the opening parenthesis of the matching closing parenthesis to the left of
the entry point. By placing the entry point next to each closing parenthesis the
programmer can check to see that all the lists are closed properly. Believe me, after
just two minutes of use you will never want to be without parenthesis matching again!
Another helpful feature of version 1.04 is a form of trace capability. In the beta
version this capability was initiated within the ªlispINIT file. When certain kinds of
errors are encountered the same kind of message is generated as was in the earlier
versions, however with this form of trace on the message is followed by each list that
was invoked and the order of occurrence. These are generated in the Listener window.
There is a drawback to this feature though, the listing can get quite long for even a
small program. The best way to debug at this time is still to break the code down into
small functions.
ExperLisp Versions
There are currently four versions of ExperLisp. Version 1.01 was the first
release. The first update was version 1.02, in which some of the routines were fixed
(i.e. MAPCAR and nested CARs and CDRs, etc.) and some routines added (i.e.
FREECONS). Version 1.03 is a version of ExperLisp which was included with
ExperOps5. Registered owners of both ExperLisp and ExperOps5 should receive
version 1.04. There are many differences between each of these versions. To see what
routines and functions are available within a version of ExperLisp type the following
in the Listener window:
(APROPOS "")
The function names will then be generated within the Listener window. Good luck,
the list is long.
The Experts Complain
Recently a letter was received by Mactutor which criticized the accuracy and
reliability of this column. I would like to say that I am NOT a Lisp programmer. That is
probably obviously apparent to one who is. The goal of this article is to be more then
just a tutorial, it is to demonstate the findings of one who is learning Lisp ON THE MAC
with only minor consulting from the experts. If you feel something is incorrect, then
by all means write to Mactutor with your comments. We welcome suggestions for
topics of interest to our readership. Let us know how we can meet your needs.